package com.shuzijun.leetcode.editor.cn;

import java.util.Arrays;
import java.util.HashMap;

public class RelativeSortArray{
    public static void main(String[] args) {
         Solution solution = new RelativeSortArray().new Solution();
         solution.relativeSortArray(new int[]{2,3,1,3,2,4,6,7,9,2,19},new int[]{2,1,4,3,9,6});
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        HashMap<Integer, Integer> counts = new HashMap<>();

        for (int i = 0; i < arr2.length; i++) {
            counts.put(arr2[i],0 );
        }

        for (int i = 0; i < arr1.length; i++) {
            if (counts.containsKey(arr1[i])){
                Integer oldCount = counts.get(arr1[i]);
                counts.put(arr1[i],oldCount+1 );
            }
        }

        int[] result = new int[arr1.length];
        int k = 0;
        for (int i = 0; i < arr2.length; i++) {
            Integer count = counts.get(arr2[i]);
            for (int j = 0; j < count; j++) {
                result[k+j] = arr2[i];
            }
            k += count;
        }

        Arrays.sort(arr1);
        for (int i = 0; i < arr1.length; i++) {
            if (!counts.containsKey(arr1[i])){
                result[k++] = arr1[i];
            }
        }

        return result;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}